package nine.test_9_5_2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Solution {
    public ArrayList<Integer> newArray (ArrayList<Integer> a) {
        // write code here
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < a.size(); i++) {
            String str = String.valueOf(a.get(i));
            String clean = str.replace("2","");

            if(! clean.isEmpty() || (clean.length() == 1 && clean.equals("0"))) {
                result.add(Integer.parseInt(clean));
            }
        }
        return result;
    }
    public ListNode mergeList (ListNode a, ListNode b) {
        // write code here
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;
        while (a != null && b != null && a.val == b.val) {
            cur.next = a;
            a = a.next;
            b = b.next;
            cur = cur.next;
        }
        Stack<ListNode> listA = new Stack<>();
        Stack<ListNode> listB = new Stack<>();
        while (a != null) {
            listA.push(a);
            a = a.next;
        }
        while (b != null) {
            listB.push(b);
            b = b.next;
        }
        Stack<ListNode> listNodes = new Stack<>();
        while (listA.size() > 0 && listB.size() > 0 && (listA.peek() == listB.peek())) {
            listNodes.push(listA.pop());
            listB.pop();
        }
        while (listNodes.size() > 0) {
            cur = listNodes.pop();
            cur = cur.next;
        }
        cur = null;
        return newHead.next;
    }
//    public int matrixCount (String[] a, int myval) {
//        // write code here
//        int n = a.length;
//        char[][] chars = new char[n][n];
//        for (int i = 0; i < a.length; i++) {
//            chars[i] = a[i].toCharArray();
//        }
//        int[][] rcount = new int[n + 1][n + 1];
//        int[][] ecount = new int[n + 1][n + 1];
//        int[][] dcount = new int[n + 1][n + 1];
//        int count = 0;
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= n; j++) {
//                rcount[i][j] = rcount[i - 1][j] + rcount[i][j - 1] - rcount[i - 1][j - 1] + (chars[i - 1][j - 1] == 'r' ? 1 : 0);
//                ecount[i][j] = ecount[i - 1][j] + ecount[i][j - 1] - ecount[i - 1][j - 1] + (chars[i - 1][j - 1] == 'e' ? 1 : 0);
//                dcount[i][j] = dcount[i - 1][j] + dcount[i][j - 1] - dcount[i - 1][j - 1] + (chars[i - 1][j - 1] == '0' ? 1 : 0);
//            }
//        }
//        for (int i = 1; i <= n; i++) {
//            for (int j = i; j <= n; j++) {
//                for (int k = 1; k <=n; k++) {
//                    for (int g = k; g <= n; g++) {
//                        int r = rcount[j][g] - rcount[i - 1][g] -rcount[j][k - 1] + rcount[i - 1][k - 1];
//                        int e = ecount[j][g] - ecount[i - 1][g] -ecount[j][k - 1] + ecount[i - 1][k - 1];
//                        int d = dcount[j][g] - dcount[i - 1][g] -dcount[j][k - 1] + dcount[i - 1][k - 1];
//                        int mincount = Math.min(r,Math.min(e,d));
//                        if(mincount >= myval) {
//                            count++;
//                        }
//                    }
//                }
//            }
//        }
//        return count;
//    }
public int matrixCount (String[] a, int myval) {
    // write code here
    int n = a.length;
    char[][] chars = new char[n][n];
    for (int i = 0; i < a.length; i++) {
        chars[i] = a[i].toCharArray();
    }
    int[][] rcount = new int[n][n];
    int[][] ecount = new int[n][n];
    int[][] dcount = new int[n][n];
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char c = chars[i][j];
            if(c == 'r') {
                rcount[i][j] = (j > 0 ? rcount[i][j - 1] : 0) + 1;
                ecount[i][j] = (j > 0 ? ecount[i][j - 1] : 0);
                dcount[i][j] = (j > 0 ? dcount[i][j - 1] : 0);
            } else if (c == 'e') {
                ecount[i][j] = (j > 0 ? ecount[i][j - 1] : 0) + 1;
                rcount[i][j] = (j > 0 ? rcount[i][j - 1] : 0);
                dcount[i][j] = (j > 0 ? dcount[i][j - 1] : 0);
            } else {
                dcount[i][j] = (j > 0 ? dcount[i][j - 1] : 0) + 1;
                ecount[i][j] = (j > 0 ? ecount[i][j - 1] : 0);
                rcount[i][j] = (j > 0 ? rcount[i][j - 1] : 0);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = i; k < n; k++) {
                for (int l = j; l < n; l++) {
                    int r = 0;
                    int e = 0;
                    int d = 0;
                    for (int m = i; m <= k; m++) {
                        r += rcount[m][1] - (j > 0 ? rcount[m][j - 1] : 0);
                        e += ecount[m][1] - (j > 0 ? ecount[m][j - 1] : 0);
                        d += dcount[m][1] - (j > 0 ? dcount[m][j - 1] : 0);
                    }
                    int min = Math.min(Math.min(r,e),d);
                    if(min >= myval) {
                        count++;
                    }
                }
            }
        }
    }
    return count;
}
    public int[] pruneSequence (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
        int max = findLong(root);
        for (int i = 0; i < max; i++) {
            ArrayList<Integer> arrayList1 = new ArrayList<>();
            arrayList.add(arrayList1);
        }
        dfs(max,root,arrayList);
        ArrayList<Integer> array = new ArrayList<>();
        for (int i = 0; i < max; i++) {
            ArrayList<Integer> arrayList1 = arrayList.get(i);
            for (int j = 0; j < arrayList1.size(); i++) {
                array.add(arrayList1.get(i));
            }
        }
        int[] arr = new int[array.size()];
        for (int i = 0; i < array.size(); i++) {
            arr[i] = array.get(i);
        }
        return arr;
    }
    private int findLong(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(findLong(root.right),findLong(root.left)) + 1;
    }
    private void dfs(int max,TreeNode root,ArrayList<ArrayList<Integer>> arrayList) {
        if(root == null) {
            return;
        }
        int left = findLong(root.left);
        arrayList.get(max - left).add(left);
        int right = findLong(root.right);
        arrayList.get(max - right).add(right);
        dfs(max,root.left,arrayList);
        dfs(max,root.right,arrayList);
    }
}
